package 我的Java学习_算法基础.day_03;

import java.util.Random;

import static 我的Java学习_算法基础.day_01.唯一成对的数.printArray;
import static 我的Java学习_算法基础.day_02._015_递归形式进行插入排序.insertSort;

public class _036_三点中值法 {
    public static void main(String[] args) {
        int[] array = new int[4];
        Random random = new Random();
        for (int i = 0 ;i<array.length;i++){
            array[i]= random.nextInt(20);
        }
        printArray(array);
        quickSort2(array,0,array.length-1);
        printArray(array);
    }
    public static void quickSort2(int[] array,int p,int r){
        if(p<r){
            if((r-p+1)<=8){    //待排序列较短时，用插入排序(排序个数<=8)
                insertSort(array,p,r);
            }else{
                int q = partition2(array,p,r);
                quickSort2(array,p,q-1);
                quickSort2(array,q+1,r);
            }

        }
    }
    public static int partition2(int[] array,int p,int r){
        //28-41为优化部分
        //优化，三点中值:在p、r、mid中选取中间值作为主元
        int mid = p +((r-p)>>1);
        int a1 =array[p],b1=array[r],c1=array[mid];
        int midIndex;
        if((a1>b1&&a1<c1)||(a1>c1&&a1<b1)){
            midIndex=p;
        }else if((b1>a1&&b1<c1)||(b1>c1&&b1<a1)){
            midIndex=r;
        }else{
            midIndex=mid;
        }
        //中值元素与首元素交换
        int swap = array[p];
        array[p] = array[midIndex];
        array[midIndex]=swap;
        int pivot = array[p];
        int left = p+1;
        int right = r;
        while(left<=right){
            while(left<=right&&array[left]<=pivot){
                left++;
            }
            while(left<=right&&array[right]>pivot){
                right--;
            }
            if(left<right){
                int a = array[left];
                array[left] = array[right];
                array[right]=a;
            }
        }
        int a = array[p];           //最后，基元与右侧指针指向元素交换
        array[p]=array[right];
        array[right]=a;
        return right;
    }
}
